//括号生成
/*正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
1 <= n <= 8
*/
class Solution {
    int left = 0;
    int right = 0;
    vector<string> ret;
    string path;

public:
    vector<string> generateParenthesis(int n) {
        dfs(n);
        return ret;
    }
    void dfs(int n) {
        if (left == n && right == n) {
            ret.push_back(path);
            return;
        }
        if (left < n) {
            path.push_back('(');
            left++;
            dfs(n);
            path.pop_back();
            left--;
        }
        if (right < left && right < n) {
            path.push_back(')');
            right++;
            dfs(n);
            path.pop_back();
            right--;
        }
    }
};

//组合
/*
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
1 <= n <= 20
1 <= k <= n
*/
class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int count = 0;

public:
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ret;
    }
    void dfs(int n, int k, int pos) {
        if (count == k) {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i <= n; i++) {
            path.push_back(i);
            count++;
            dfs(n, k, i + 1);
            path.pop_back();
            count--;
        }
    }
};

//组合总和
/*给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
*/
class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int sum = 0;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return ret;
    }
    void dfs(vector<int>& candidates, int& target, int pos) {
        if (sum == target) {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i < candidates.size(); i++) {
            if (sum < target) {
                path.push_back(candidates[i]);
                sum += candidates[i];
                dfs(candidates, target, i);
                path.pop_back();
                sum -= candidates[i];
            }
        }
    }
};
